﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using Heap;
using AbstractHeap;

namespace ArrayHeap {
    public class Heap<T> : AbstractHeap<T> {
        private const uint DefaultDim = 4;
        private readonly IComparer<T> _comparer;
        private T[] _elems;
        private uint _lastElemIndex;

        public Heap(IComparer<T> comparer) {
            if(comparer==null)
                throw new ArgumentNullException("comparer");
            _comparer = comparer;
            _elems = new T[DefaultDim];
            _lastElemIndex = 0;
        }

        public Heap(IComparer<T> comparer, uint dim) {
            if(comparer==null)
                throw new ArgumentNullException("comparer");
            _comparer = comparer;
            _elems=new T[dim];
            _lastElemIndex = 0;
        } 

        public Heap(IComparer<T> comparer, T[] elems, uint lastElemIndex) {
            if(comparer==null)
                throw new ArgumentNullException("comparer");
            _comparer = comparer;
            _elems = elems;
            _lastElemIndex = lastElemIndex;
        }

       public override IEnumerator<T> GetEnumerator() {
            return new HeapEnumerator(this); 
        }
        
        public override bool Equals(object obj) {
            if (obj == null)
                return false;
            if (!(obj is Heap<T>)) return true;
            var castedObj = (Heap<T>) obj;
            return _elems.SequenceEqual(castedObj._elems) && _comparer.Equals(castedObj._comparer);
        }

        public override int GetHashCode() {
            Debug.Assert(_elems != null, "_elems != null");
            return _elems.GetHashCode()^_comparer.GetHashCode();
        }

        public override string ToString() {
            var res = "Heap: { Comparator: "+_comparer+"; Elements: [";
            res = _elems.Aggregate(res, (current, elem) => current + (elem + " "));
            res += "] }";
            return res;
        }

        public override T FindMin() {
            CheckIsNotEmpty();
            return _elems[1];
        }

        public override void ChangeKey(T oldKey, T newKey) {
            if (_comparer.Compare(oldKey,newKey)==0)
                return;
            var index = GetElementIndex(oldKey);
            _elems[index] = newKey;
            if (_comparer.Compare(oldKey,newKey)<0)
                MoveDown(index);
            else 
                if (_comparer.Compare(oldKey, newKey) > 0)
                    MoveUp(index);
        }

        public override void Insert(T item) {
            if (_lastElemIndex == (_elems.Length - 1))
                IncreaseDimension();
            _elems[++_lastElemIndex] = item;
            MoveUp(_lastElemIndex);
        }

        public override uint Size() {
            return _lastElemIndex;
        }

        public override bool IsEmpty() {
            return _lastElemIndex == 0;
        }

        public override T ExtractMin() {
            CheckIsNotEmpty();
            var min = _elems[1];
            if (_lastElemIndex == 1)
                _lastElemIndex = 0;
            else {
                _elems[1] = _elems[_lastElemIndex--];
                MoveDown(1);
            }
            return min;
        }

        private void CheckIsNotEmpty() {
            if (IsEmpty())
                throw new NullReferenceException("There isn't any elem in the heap");
        }

        public override void MoveDown(T item) {
            var index = GetElementIndex(item);
            MoveDown(index);
        }

        private void MoveDown(uint index) {
            var item=_elems[index];
            var j = 2*index;
            while (j <= _lastElemIndex && (_comparer.Compare(item, _elems[j]) > 0 || (j+1 <= _lastElemIndex && _comparer.Compare(item,_elems[j+1])>0))) {
                if (j + 1 <= _lastElemIndex && _comparer.Compare(_elems[j + 1], _elems[j]) < 0)
                    j++;
                _elems[index] = _elems[j];
                index = j;
                j = 2*index;
            }
            _elems[index] = item;
        }

        public override void MoveUp(T item) {
            var index = GetElementIndex(item);
            MoveUp(index);
        }

        public override bool Contains(T item) {
            for(var i=1;i<=_lastElemIndex;i++)
                if (_elems[i].Equals(item))
                    return true;
            return false;
        }

        private void MoveUp(uint index) {
            var item=_elems[index];
            while (index > 1 && _comparer.Compare(item, _elems[index/2]) < 0) {
                _elems[index] = _elems[index/2];
                index = index/2;
            }
            _elems[index] = item;
        }

        private uint GetElementIndex(T item) {
            if (!Contains(item))
                throw new ArgumentException("There is not this elem in the heap");
            uint index = 1;
            while (!_elems[index].Equals(item))
                index++;
            return index;
        }

        private void IncreaseDimension(){
            var nuovo = new T[_elems.Length * 2];
            _elems.CopyTo(nuovo, 0);
            _elems = nuovo;
        }

        private class HeapEnumerator : IEnumerator<T> {
            private readonly Heap<T> _heap;
            private uint _currentIndex;

            public HeapEnumerator(Heap<T> heap) {
                _heap = heap;
            }

            public void Dispose() { }

            public bool MoveNext() {
                return ++_currentIndex <= _heap._lastElemIndex;
            }

            public void Reset() {
                _currentIndex = 0;
            }

            public T Current {
                get { return _heap._elems[_currentIndex]; }
            }

            object IEnumerator.Current {
                get { return Current; }
            }
        }
    }
}